package com.example.collection;

import com.example.calculation.TopResult;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class TopKList extends AbstractList<TopResult>
        implements List<TopResult>, RandomAccess, Cloneable, java.io.Serializable{

    transient TopResult[] elementData; // non-private to simplify nested class access

    private int topK;
    private int topKValue = 0;
    private int size = 0;

    private int capacity = 0;

    int[] scores;

    public List<TopResult> removes = new ArrayList<TopResult>(capacity);

    public static void main(String[] args) {
        TopKList topKList = new TopKList(50000, 30000);
        ArrayList<TopResult> topResults = new ArrayList<TopResult>();
        Random random = ThreadLocalRandom.current();
        for (int i = 0; i < 1000000; i++) {
            int i1 = random.nextInt(1000000);

            TopResult topResult = new TopResult(null, null, i1);
            topResults.add(topResult);
            topKList.add(topResult);
        }
        topResults.sort(new Comparator<TopResult>(){
            @Override
            public int compare(TopResult o1, TopResult o2) {
                return o2.score - o1.score;
            }
        });
        topResults.subList(0,30000);

        ArrayList<TopResult> topResults2 = new ArrayList<TopResult>();

        int min = 99999999 ;
        for (int i = 0; i < topKList.size(); i++) {
            topResults2.add(topKList.get(i));
            if (min>topKList.get(i).score){
                min=topKList.get(i).score;
            }
        }

        System.out.println(topResults.get(29999).score);
        System.out.println(min);
    }

    public TopKList(int capacity, int topK) {
        this.capacity = capacity;
        if (topK > capacity) {
            topK = capacity;
        }
        this.topK = topK;
        elementData = new TopResult[this.capacity];
        scores = new int[this.capacity];
    }

    @Override
    public TopResult get(int index) {
        if (index < capacity)
            return elementData[index];
        else return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean add(TopResult e) {
        return addAndSort(e);
    }


    @Override
    public TopResult remove(int index) {
        return null;
    }


    /**
     * 返回是否添加成功
     */
    public boolean addAndSort(TopResult e) {
        if (size < capacity && topKValue <= e.score) {
            elementData[size] = e;
            scores[size++] = e.score;
            return true;
        } else if (size == capacity) {
            sortImmediately();
//            if (size == capacity) {  //应该没这么极端的情况
//                return false;
//            }
            if (topKValue <= e.score) {
                elementData[size] = e;
                scores[size++] = e.score;
                return true;
            }
            return false;
        }
        return false;
    }


    public boolean sortImmediately() {

        // capacity-topK  找出第 i 小的数
        int topKValue = bfprt(scores, 0, scores.length - 1, capacity-topK);
        int position = 0;
        int length = size;
        TopResult[] temp = this.elementData;
        for (int i = 0; i < length; i++) {
            TopResult topResult = temp[i];
            temp[i] = null;
            if (topResult.score >= topKValue) {
                temp[position] = topResult;
                scores[position++] = topResult.score;
            } else {
                removes.add(topResult);
            }
        }
        size = position;
        this.topKValue = topKValue;
        return true;
    }

    /**
     * The recursive procedure in BFPRT.
     *
     * @param arr The array from which select.
     * @param p   The start index of the sub-array from which select.
     * @param r   The end index of the sub-array from which select.
     * @param i   The order of the element to be selected.
     * @return The selected element.
     */
    protected int bfprt(int[] arr, int p, int r, int i) {
        if (p == r) {
            return arr[p];
        }
        int pivot = medianOfMedians(arr, p, r);
        int[] pivotRange = partition(arr, p, r, pivot);
        if (p + i >= pivotRange[0] && p + i <= pivotRange[1]) {
            return arr[pivotRange[0]];
        } else if (p + i < pivotRange[0]) {
            return bfprt(arr, p, pivotRange[0] - 1, i);
        } else {
            return bfprt(arr, pivotRange[1] + 1, r, i + p - pivotRange[1] - 1);
        }
    }

    /**
     * Compute the median of the medians of the input array.
     *
     * @param arr The array to be computed.
     * @param p   The start index of the sub-array.
     * @param r   The end index of the sub-array.
     * @return The median of the medians of the sub-array.
     */
    protected int medianOfMedians(int[] arr, int p, int r) {
        int num = r - p + 1;
        int extra = num % 5 == 0 ? 0 : 1;
        int[] medians = new int[num / 5 + extra];
        for (int i = 0; i < medians.length; i++) {
            medians[i] = computeMedian(arr, p + i * 5, Math.min(p + i * 5 + 4, r));
        }
        return bfprt(medians, 0, medians.length - 1, medians.length / 2);
    }

    /**
     * Partition the array into two parts.
     * <p>
     * After this method, elements less than pivot are put left, pivots are put middle, others are put right.
     *
     * @param arr The array to be sorted.
     * @param p   The start index of the sub-array to be sorted.
     * @param r   The end index of the sub-array to be sorted.
     * @return A two elements array. The first element indicates the index of the first pivot, the second element
     * indicates the index of the last pivot.
     */
    protected int[] partition(int[] arr, int p, int r, int pivot) {
        int small = p - 1;
        int equal = 0;
        int temp;
        for (int j = p; j <= r; j++) {
            if (arr[j] < pivot) {
                small++;
                temp = arr[small];
                arr[small] = arr[j];
                if (equal > 0) {
                    arr[j] = arr[small + equal];
                    arr[small + equal] = temp;
                } else {
                    arr[j] = temp;
                }
            } else if (arr[j] == pivot) {
                equal++;
                temp = arr[j];
                arr[j] = arr[small + equal];
                arr[small + equal] = temp;
            }
        }
        return new int[]{small + 1, small + equal};
    }

    /**
     * Compute the median of the given array.
     *
     * @param arr   Array to be computed.
     * @param begin The begin index of the range to be computed.
     * @param end   The end index of the range to be computed.
     * @return The median of the array in the specified range.
     */
    private int computeMedian(int[] arr, int begin, int end) {
        Arrays.sort(arr, begin, end + 1);
        return arr[begin + (end - begin) / 2];
    }

}
